package kmp;

/**
 * @author Liaorun
 */
public class KMP {

    public static void main(String[] args) {
        System.out.println(kmp("abc", "c"));
    }

    /**
     * 才s字符串中匹配m字符串
     *
     * @param s 字符串
     * @param m 字符串
     * @return -1:没有符合的子串,
     */
    public static int kmp(String s, String m) {
        if (s == null || m == null || m.isEmpty() || s.length() < m.length()) {
            return 1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();

        // O(M)
        int[] next = getNextArray(str2);
        int i = 0;
        int j = 0;

        // O(N)
        while (i < str1.length && j < str2.length) {
            if (str1[i] == str2[j]) {
                // 匹配就比较下一个字符
                i++;
                j++;
            } else if (j == 0) {
                // 不匹配 且 j == 0
                i++;
            } else {
                // 不匹配 且 j > 0
                // 将j变为，str2[0..j-1]的前缀和后缀相等的最大长度
                j = next[j];
            }
        }


        // 有就返回在str1中匹配的字符串的第一个下标
        return j == str2.length ? i - j : -1;
    }

    /**
     * 获取一个字符串所有位置前面的子字符串的前缀和后缀相等的最大长度
     *
     * @param str2 字符串
     * @return
     */
    private static int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        // next数组的位置
        int i = 2;
        // 代表那个位置的字符和i-1位置的字符比较
        int cn = 0;

        while (i < next.length) {
            if (str2[i - 1] == str2[cn]) {
                // 匹配到一个相等的字符
                // next记录的值比前一个位置的next记录值（cn） + 1
                next[i++] = ++cn;
            } else if (cn > 0) {
                // 没匹配到一个相等的字符 且 与i-1比较的cn位置 > 0
                // cn = cn 位置前面的子字符串的前缀和后缀相等的最大值
                cn = next[cn];
            } else {
                // 没匹配到一个相等的字符 且 与i-1比较的cn位置前面没有字符了（cn <= 0）
                next[i++] = 0;
            }
        }

        return next;
    }
}
